Complexidade computacional

A Teoría da Complexidade Computacional é unha rama da teoría da computación que se centra na clasificación dos problemas computacionais de acordo á súa dificultade inherente, e na relación entre devanditas clases de complexidade.

Un problema catalógase como "inherentemente difícil" se a súa solución require dunha cantidade significativa de recursos computacionais, sen importar o algoritmo empregado. A teoría da complexidade computacional formaliza dita aseveración, introducindo modelos de cómputo matemáticos para o estudo destes problemas e a cuantificación da cantidade de recursos necesarios para resolvelos, como tempo e memoria.

Un dos fins da teoría da complexidade computacional é determinar os límites prácticos de que é o que se pode facer nunha computadora e que non. Outros campos relacionados coa teoría da complexidade computacional son a análise de algoritmos e a teoría da computabilidade. Unha diferenza significativa entre a análise de algoritmos e a teoría da complexidade computacional, é que a primeira se dedica a determinar a cantidade de recursos requiridos por un algoritmo en particular para resolver un problema, mentres que a segunda, analiza todos os posibles algoritmos que puidesen ser usados para resolver o mesmo problema.

A teoría da complexidade computacional trata de clasificar os problemas que poden ou non poden ser resoltos cunha cantidade determinada de recursos. Á súa vez, a imposición de restricións sobre estes recursos é o que a distingue da teoría da computabilidade, que se preocupa por que tipo de problemas poden ser resoltos de maneira algorítmica.